package string;

/**
 * Longest Common Substring
 * Longuest Common Palindrome
 * 
 * Timing Complexity: O(n.m)
 * 
 * */
public class LCSubstr {

	
	/**
	 * finds out longest common substring of two given strings. Returns longest common 
	 * palindrome if second string is reverse of first string
	 * 
	 * @param  first string
	 * @param  second string
	 * 
	 * @return  longest common substring 
	 * */
	public static String findMaxLength(String str1, String str2){
		
		int len1 = str1.length();
		int len2 = str2.length();
		int maxLenSubstr = 0;
		int startIndexMaxSubstr = 0;
		
		int[][] matrix = new int[len1 + 1][len2 + 1];
		
		for(int i = 0; i < len1; i++){
			for(int j = 0; j < len2; j++){
				
				if(str1.charAt(i) == str2.charAt(j)){
					matrix[i+1][j+1] = matrix[i][j] + 1;
					
					if(matrix[i+1][j+1] > maxLenSubstr){
						maxLenSubstr = matrix[i+1][j+1];
						// calculate start index of longest substring in str2
						startIndexMaxSubstr = j - maxLenSubstr + 1;
					}
				}
			}
		}
		
		return str2.substring(startIndexMaxSubstr, startIndexMaxSubstr + maxLenSubstr);
	}
	
	
	public static void main(String[] args){
		System.out.println(findMaxLength("abab", "baba"));
		//System.out.println(findMaxLength("ilikeracecarstoomuch", "hcumootsracecarekili"));
	}
}
